package 零钱兑换;
//动态规划
public class Solution1 {
    public int coinChange(int[] coins, int amount) {
        if (amount < 1) {
            return 0;
        }
        int[] counts = new int[amount];
        return coincha(coins,amount,counts);

    }

    public int coincha(int[] coins , int amount , int[] counts){
        if(amount == 0){
            return 0;
        }
        if(amount < 0){
            return -1;
        }
        if(counts[amount-1]!=0){
            return counts[amount-1];
        }
        //次数先设为最大值最大
        int min = Integer.MAX_VALUE;

        for (int coin:coins) {
            int res = coincha(coins,amount-coin,counts);
            if(res >= 0 && res <min);
            min = res+1;
        }

        counts[amount -1] = min==Integer.MAX_VALUE ? -1:min;
        return counts[amount-1];
    }

}
